Magic squares in grid [Brute Force]¶
Time: O(MxN); Space: O(1); easy
A 3 x 3 magic square is a 3 x 3 grid filled with distinct numbers from 1 to 9 such that each row, column, and both diagonals all have the same sum.
Given an grid of integers, how many 3 x 3 “magic square” subgrids are there? (Each subgrid is contiguous).
Example 1:
Input:
grid = [[4, 3, 8, 4], [9, 5, 1, 9], [2, 7, 6, 2]] Output: 1
Explanation:
The following subgrid is a 3 x 3 magic square:
3 8
5 1
7 6 while this one is not:
8 4
1 9
6 2
In total, there is only one magic square inside the given grid.
Notes:
1 <= grid.length <= 10
1 <= grid[0].length <= 10
0 <= grid[i][j] <= 15
Intuition and Algorithm Let’s check every 3x3 grid individually. For each grid, all numbers must be unique and between 1 and 9; plus every row, column, and diagonal must have the same sum.
Extra Credit We could also include an if grid[r+1][c+1] != 5: continue check into our code, helping us skip over our for r… for c… for loops faster. This is based on the following observations:
The sum of the grid must be 45, as it is the sum of the distinct values from 1 to 9. Each horizontal and vertical line must add up to 15, as the sum of 3 of these lines equals the sum of the whole grid. The diagonal lines must also sum to 15, by definition of the problem statement. Adding the 12 values from the four lines that cross the center, these 4 lines add up to 60; but they also add up to the entire grid (45), plus 3 times the middle value. This implies the middle value is 5.
[1]:
class Solution1(object):
def numMagicSquaresInside(self, grid) -> int:
"""
:type grid: List[List[int]]
:rtype: int
"""
R, C = len(grid), len(grid[0])
def is_magic(a,b,c,d,e,f,g,h,i):
return (sorted([a,b,c,d,e,f,g,h,i]) == [x for x in range(1, 10)] and
(a+b+c == d+e+f == g+h+i ==
a+d+g == b+e+h == c+f+i ==
a+e+i == c+e+g == 15))
result = 0
for r in range(R - 2):
for c in range(C - 2):
if grid[r + 1][c + 1] != 5:
continue # optional skip
if is_magic(grid[r][c],
grid[r][c + 1],
grid[r][c + 2],
grid[r + 1][c],
grid[r + 1][c + 1],
grid[r + 1][c + 2],
grid[r + 2][c],
grid[r + 2][c + 1],
grid[r + 2][c + 2]):
result += 1
return result
[2]:
grid = [[4, 3, 8, 4],
[9, 5, 1, 9],
[2, 7, 6, 2]
]
s = Solution1()
assert s.numMagicSquaresInside(grid) == 1
[3]:
class Solution2(object):
def numMagicSquaresInside(self, grid) -> int:
"""
:type grid: List[List[int]]
:rtype: int
"""
def is_magic(grid, r, c):
expect = k * (k**2 + 1) // 2
nums = set()
min_num = float("inf")
sum_diag, sum_anti = 0, 0
for i in range(k):
sum_diag += grid[r + i][c + i]
sum_anti += grid[r + i][c + k - 1 - i]
sum_r, sum_c = 0, 0
for j in range(k):
min_num = min(min_num, grid[r+i][c+j])
nums.add(grid[r + i][c + j])
sum_r += grid[r + i][c + j]
sum_c += grid[r + j][c + i]
if not (sum_r == sum_c == expect):
return False
return sum_diag == sum_anti == expect and \
len(nums) == k**2 and \
min_num == 1
k = 3
result = 0
for r in range(len(grid) - k + 1):
for c in range(len(grid[r]) - k + 1):
if is_magic(grid, r, c):
result += 1
return result
[4]:
grid = [[4, 3, 8, 4],
[9, 5, 1, 9],
[2, 7, 6, 2]
]
s = Solution2()
assert s.numMagicSquaresInside(grid) == 1